package 中等.树;

import util.TreeNode;

/**
 * 序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链
 * 路传输，以便稍后在同一个或另一个计算机环境中重建。
 * 设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。
 * 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。
 * 编码的字符串应尽可能紧凑。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/serialize-and-deserialize-bst
 */
public class 序列化和反序列化二叉搜索树_449 {

    public static void main(String[] args) {

        TreeNode node2 = new TreeNode(2);
        TreeNode node1 = new TreeNode(1);
        node1.right = node2;
        Codec codec = new Codec();
        System.out.println(codec.serialize(node1));
        TreeNode deserialize = codec.deserialize(codec.serialize(node1));
        System.out.println(deserialize);

    }

}

/**
 * 先序遍历+BST特性+二分查找
 * 先序遍历之后，节点之间用逗号分割，子树为null时不记录，节省空间
 * 得到一个数组，preNums[0,n-1] 的数组，先序遍历的特性，preNums[0]一定是根节点
 * <p>
 * 根据BST特性，leftNode < root < rightNode ，已知 preNums[0] == root 根节点
 * 那么在 preNums[0,n-1] 数组中，一定存在一个索引位置 j , 使得 preNums[j,n-1]
 * 所有的值，> preNums[0] ,preNums[0+1,j-1] 中的值是小于 preNums[0] 的
 * <p>
 * 使用递归来构造数，二分查找来找到，大于 preNums[0]，的第一个索引 j
 */
class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "";
        // 直接使用字符串构建，去除最后一个逗号
        StringBuilder builder = new StringBuilder();
        preSort(root, builder);
        return builder.substring(0, builder.length() - 1);
    }

    private void preSort(TreeNode node, StringBuilder builder) {
        if (node == null) return;
        builder.append(node.val).append(",");
        preSort(node.left, builder);
        preSort(node.right, builder);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == "") return null;
        String[] datas = data.split(",");
        return deserialize(0, datas.length - 1, datas);
    }

    private TreeNode deserialize(int left, int right, String[] datas) {
        if (left > right) return null;
        int rootVal = Integer.parseInt(datas[left]);
        TreeNode root = new TreeNode(rootVal);
        int j = search(rootVal, left + 1, right, datas);
        root.right = deserialize(j, right, datas);
        root.left = deserialize(left + 1, j - 1, datas);
        return root;
    }

    // 二分查找
    private int search(int num, int left, int right, String[] datas) {
        int ans = right + 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int curNum = Integer.parseInt(datas[mid]);
            if (curNum >= num) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

}